module type ComplexSig = sig
    type t
    val zero : t
    val add : t -> t -> t
end

module Complex: ComplexSig = struct
    type t = float * float

    let zero = (0., 0.)

    let add (x0, y0) (x1, y1) = (x0 +. x1, y0 +. y1)
end


module type Queue = sig
    type 'a t

    val enqueue: 'a -> 'a t -> 'a t

    val dequeue: 'a t -> 'a t

    val peek: 'a t -> 'a

    val empty: 'a t
end

module ListQueue: Queue = struct
    type 'a t = { in_queue: 'a list; out_queue: 'a list }

    let empty = {in_queue = []; out_queue = []}

    let enqueue value = function
        | {in_queue; out_queue = h::t} -> {in_queue = value::in_queue; out_queue = h::t}
        | {in_queue = []; out_queue = []} -> {in_queue = []; out_queue = value::[]}
        | {in_queue; out_queue = []} -> {in_queue = []; out_queue = List.rev in_queue}

    let dequeue = function
        | {in_queue; out_queue = []} -> failwith "empty"
        | {in_queue; out_queue = h::[]} -> {in_queue = []; out_queue = List.rev in_queue}
        | {in_queue; out_queue = h::h'::t} -> {in_queue; out_queue = h'::t}

    let peek = function
        | {out_queue = []} -> failwith "empty"
        | {out_queue = h::t} -> h
end

(* Creates a ListQueue filled with [n] elements. *)
let fill_listqueue n =
  let rec loop n q =
    if n=0 then q
    else loop (n-1) (ListQueue.enqueue n q) in
  loop n ListQueue.empty
